package 算法.leetcode.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author lchenglong
 * @date 2022/3/21
 */
public class Offer56_II {

    public static void main(String[] args) {
        Offer56_II instance = new Offer56_II();
        int[] nums = new int[]{9,2,7,9,7,9,7};
        int res = instance.singleNumber3(nums);
        System.out.println(res);
    }
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> dic = new HashMap<Integer, Integer>();
        for (int n:nums){
            Integer value = dic.get(n);
            if (null == value){
                dic.put(n,1);
            } else if (value < 2){
                dic.put(n,2);
            }else if (value == 2){
                dic.remove(n);
            }
        }
        int res =0;
        for (Integer n: dic.keySet()){
            res = n;
        }
        return res;
    }

    /**
     * 有限状态机
     * 所有位相加%3，所得位为0，1，2； 用两位表示，分别为ones,twos;
     * @param nums
     * @return
     */
    public int singleNumber2(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }

    /**
     * 有限状态机
     * 所有位相加%3，所得位为0，1，2； 用两位表示，分别为ones,twos;
     * @param nums
     * @return
     */
    public int singleNumber3(int[] nums) {
        // 数组中所有的数每个位相加
        int[] bitArr = new int[32];
        for (int n:nums){
            for (int i = 0;i<32;i++) {
                bitArr[i] += n & 1;
                // 无符号右移1位
                n >>>=1;
            }
        }
        int res = 0,m=3;
        // 从高位依次放到res中
        for (int i=0;i<32;i++) {
            res <<=1;
            res |= bitArr[31-i] %m;
        }
        return res;
    }
}
